#include<bits/stdc++.h>
using namespace std;

bool visited[12][12];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

/*字典树部分*/
int trie[700][26];
int len = 0;

void trie_insert(const string& word) {
    int temp = 0, new_node;
    for(int i = 0; i < word.length(); i++){
        new_node = trie[temp][word[i] - 'a'];
        if(!new_node){
            len++;
            new_node = -len;
            if(i == word.length() - 1) new_node = -new_node;
            trie[temp][word[i] - 'a'] = new_node;
            temp = abs(new_node);
        }
        else{
            if(i == word.length() - 1) trie[temp][word[i] - 'a'] = abs(new_node);
            temp = abs(new_node);
        } 
    }
}

vector<string> ans;

bool trie_starts_with(const string& prefix){
    int pos = 0, temp = 0, pre;
    while(pos < prefix.length()){
        if(!trie[temp][prefix[pos] - 'a'])return false;
        pre = temp;
        temp = abs(trie[temp][prefix[pos] - 'a']);
        pos++;
    }
    if(trie[pre][prefix[pos - 1] - 'a'] > 0){
        ans.push_back(prefix);
        trie[pre][prefix[pos - 1] - 'a'] = -trie[pre][prefix[pos - 1] - 'a'];
    }
    return true;
}

vector<vector<char>>* board;
string temp = "";

void dfs(int x, int y){
    temp += (*board)[x][y];
    visited[x][y] = true;

    if(trie_starts_with(temp)){
        int tx, ty;
        for(int i = 0; i < 4; i++){
            tx = x + dir[i][0];
            ty = y + dir[i][1];
            if(tx >= 0 && ty >= 0 && tx < board->size() && ty < (*board)[tx].size() && !visited[tx][ty]){
                dfs(tx, ty);
            }
        }
    }
    temp.pop_back();
    visited[x][y] = false;
}

class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        memset(trie, 0, sizeof(trie));
        ::len = 0;
        ans.clear();

        for(int i = 0; i < words.size(); i++)trie_insert(words[i]);
        
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[i].size(); j++){
                memset(visited, false, sizeof(visited));
                ::board = &board;
                temp = "";
                dfs(i, j);
            }
        }
        return ans;
    }
};

/**
 * 2021.9.16
 * 回溯 + 前缀树
 */